package com.zxy.javaarithmetic.LinearList;

import com.zxy.javaarithmetic.Utils;

/**
 * @author : Shonn.Zhang
 * @email : shonn.zhang@mart.blue
 * @time : 2021/8/27 11:42
 * @desc : 归并排序 （稳定排序，非原地排序），时间复杂度稳定在O(nlogn)
 *         递归实现，注意递归结束条件
 *
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 6, 9, 3, 4, 6, 10, 8};
        Utils.print(arr, 0, arr.length - 1);
        mergeSort(arr, 0, arr.length - 1);
        Utils.print(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr,int l,int r){
        //递归结束条件：排序数组个数小于等于1
        if((r - l) <= 0) return;

        //注意：int的边界以及移位比除法效率更高
        int k = l + ((r - l) >> 1);
        mergeSort(arr,l,k);
        mergeSort(arr,k+1,r);

        merge(arr,l,k,k+1,r);
    }

    private static void merge(int[] arr,int l1,int r1,int l2,int r2){
        int[] res = new int[r2 - l1 + 1];
        int resPos = 0;
        int start = l1;

        while(l1 <= r1 && l2 <= r2){
            if(arr[l1] <= arr[l2]){
                res[resPos++] = arr[l1++];
            }else {
                res[resPos++] = arr[l2++];
            }
        }

        int l = l1 ;
        int r = r1;
        if(l2 <= r2){
            l = l2;
            r = r2;
        }
        for(;l <= r;l++){
            res[resPos++] = arr[l];
        }

        for (resPos = 0; resPos < res.length; resPos++) {
            arr[start++] = res[resPos];
        }
    }
}
